home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c++-part1 / 9055 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.1 KB
  1. Path: ix.netcom.com!netnews
  2. From: wkdugan@ix.netcom.com (Bill Dugan)
  3. Newsgroups: comp.lang.c++
  4. Subject: Re: fast sorted-list implementation for event-based sim?
  5. Date: Wed, 28 Feb 1996 07:26:40 GMT
  6. Organization: Netcom
  7. Message-ID: <4h106b$sqa@cloner4.netcom.com>
  8. References: <Pine.SGI.3.91.960227110848.17017C-100000@golgi>
  9. NNTP-Posting-Host: lax-ca9-17.ix.netcom.com
  10. X-NETCOM-Date: Tue Feb 27 11:28:11 PM PST 1996
  11. X-Newsreader: Forte Free Agent 1.0.82
  12.  
  13. Take a look at the priority queue in the Standard Template Library. I
  14. think it's pretty close to what you're asking for.
  15.  
  16. Joseph Strout <jstrout@ucsd.edu> wrote:
  17.  
  18. >I'm considering writing an event-based simulation package.  The needs are 
  19. >simple: events go into a collection with an event-time; they may be put 
  20. >in in any order (though in general, they will be entered in rough order).
  21. >They need to be taken out in order.  Both operations need to be very fast.
  22.  
  23. >I've just examined one implementation of such a thing, that builds a big 
  24. >(fixed-size) array of events.  To insert an event, it crawls through the 
  25. >array to the first unused slot and sticks it there.  To find the next 
  26. >event, it goes through all events sequentially, and finds the one with 
  27. >the earliest event time.
  28.  
  29. >Surely this could be done better?  With a dynamically-allocated linked 
  30. >list, for example, we could insert freely at the end of the list, and do 
  31. >the Find as above.  Or will all that new'ing and delete'ing slow me down?
  32.  
  33. >Perhaps it would be better to maintain the list in sorted order in the 
  34. >first place (i.e., as each event is inserted).  This could be done with a 
  35. >b-tree structure, I suppose.  (Are there any publicly available 
  36. >implementations of such a data structure?)
  37.  
  38. >Any advice would be greatly appreciated.  This will be used for 
  39. >educational/research freeware, not for commercial purposes.
  40.  
  41. >,------------------------------------------------------------------.
  42. >|    Joseph J. Strout           Department of Neuroscience, UCSD   |
  43. >|    jstrout@ucsd.edu           http://www-acs.ucsd.edu/~jstrout/  |
  44. >`------------------------------------------------------------------'
  45.  
  46.  
  47.  
  48.